import java.util.*;

public class Solution {
//    List<Integer> path = new ArrayList<>();
//    List<List<Integer>> ans = new ArrayList<>();
//    public void DFS(int n, int k, int cur){
//        if(path.size() == k){
//            ans.add(new ArrayList<>(path));
//            return;
//        }
//
//        for(int i = cur; i <= n; i++){
//            path.add(i);
//            DFS(n, k, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    public List<List<Integer>> combine(int n, int k) {
//       DFS(n, k, 1);
//       return ans;
//    }
//
//    public static void main(String[] args) {
//        List<List<Integer>> tmp = new Solution().combine(4,2);
//        for(int i = 0; i < tmp.size(); i++){
//            for(int j = 0; j < tmp.get(i).size(); j++){
//                System.out.print(tmp.get(i).get(j) + ",");
//            }
//            System.out.println();
//        }
//
//    }

    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();

    void DFS(int k, int n, int cur){
        if(path.size() == k){
            int sum = 0;
            for(int i = 0; i < path.size(); i++){
                sum += path.get(i);
            }
            if(sum == n){
                ans.add(new LinkedList<Integer>(path));
            }
            return;
        }

        for(int i = cur; i <= 9; i++){
        path.add(i);
        DFS(k, n, i + 1);
        path.removeLast();
    }
}

    public List<List<Integer>> combinationSum3(int k, int n) {
        DFS(k, n, 1);
        return ans;
    }
}
